Corelab Seminar
2017-2018
Panayotis Mertikopoulos
Traffic Routing: Efficiency, Equilibrium and Dynamics
Abstract.
Traffic routing in congested networks is a notoriously
difficult problem, usually leading to droves of disgruntled commuters.
The most widely used measure of inefficiency for such problems is the
so-called price of anarchy, i.e. the ratio between the aggregate latency
at equilibrium (that is, when each individual traffic element is
unilaterally satisfied with its choice of path) and the least possible
aggregate latency. Depending on the structure of the network and its
delay functions, different worst-case bounds have been established for
the price of anarchy, perhaps the most famous of which is the 4/3 bound
of Roughgarden and Tardos (2002) for networks with affine costs. In
practice however, the price of anarchy tends to be significantly lower
than these worst-case bounds would suggest, and several empirical
studies in real-world networks show that it becomes negligible in both
light and heavy traffic. This talk will focus on whether this disconnect
between theory and practice can be justified theoretically, and what
kind of algorithmic schemes can be used to steer a traffic network to
equilibrium in an efficient manner.